package class07

import (
	"math"
	"sort"
)

/*
	给定一个正数数组arr,其中所有的值都为整数，以下是最小不可组成的概念：
	把 arr 每个子集内的所有元素加起来会出现很多值，其中最小的记为min，最大的记为max 在区间[min, max]上。
	如果有数不可以被arr的某一个子集相加得到，那么其中的那个数是arr的最小不可组成和 在区间[min,max]上，如果
	所有的数都可以被arr的某一个子集相加得到，那么max+1是arr的最小不可组成和

	【举例】
	arr = [3,2,5]  子集{2}相加产生2为min，子集{3,2,5}相加产生 10 为 max。在区间[2,10] 上，4，6 和 9
	不能被任何子集相加得到，其中4是arr的最小不可组成和。arr=[1,2,4]。子集{1}相加产生1为min，子集{1,2,4}相加
	产生7为max。在区间[1,7]上，任何数都可以被子集相加得到，所以8是arr的最小不可组成和。
	【进阶】
	如果已知正整数数组arr中肯定有1这个数，是否能更快地得到最小不可组成和。

	【解法】
		采用背包问题的解法，生成二维表  dp[i][j] 表示 物品0-i是否可以刚好满容量为j的大小
				0 .... max
		0
		1
		.
		.
		.
		N-1		?   ....  ?       遍历最后一行，第一个false对应的横坐标即为答案。

	【进阶问题解法】N*logN
		0-range 表示当前位置，之前的可以做到的连续的最小不可组成和的范围
		到了 i 位置，进行判断
			如果 arr[i] > range+1
				直接返回 arr[i]
			如果 arr[i] <= range+1
				range += arr[i]
		假设：
			1. i 位置 为3 range 为 5
			2. 过了i，range 需要变为：8
*/
// 1. 暴力解，采用收集所有组合的sum，加入集合后，遍历区间找到集合不存在的值，并返回
func UnformedSumViolent(arr []int) int {
	if len(arr) == 0 {
		return 1
	}
	uSumSet := make(map[int]struct{})
	UnformedSumViolentProcess(arr, 0, 0, uSumSet)
	arrMin := math.MaxInt
	for i:=0; i<len(arr); i++ {
		arrMin = min(arrMin, arr[i])
	}
	for i:=arrMin+1; i!=math.MinInt; i++ {
		if _, ok := uSumSet[i]; !ok {
			return i
		}
	}
	return 0
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}


// start表示当前位置，sum表示累加和,set用于记录累加和
func UnformedSumViolentProcess(arr []int, start, sum int, set map[int]struct{}){
	if start == len(arr) {
		set[sum] = struct{}{}
		return
	}
	UnformedSumViolentProcess(arr, start+1, sum+arr[start], set)
	UnformedSumViolentProcess(arr, start+1, sum, set)
}

// 2. 背包思路解法，采用二维表，填写状态，遍历区间，返回结果值
func UnformedSumPaketResolve(arr []int) int {
	if len(arr) == 0 {
		return 1
	}
	packetSize := 0
	minUSum := math.MaxInt
	for _, n := range arr {
		packetSize += n
		minUSum = min(minUSum, n)
	}
	dp := make([][]bool, len(arr))
	for i:=0; i<len(dp); i++ {
		dp[i] = make([]bool, packetSize+1)
	}
	// 初始化第一列
	for i:=0; i<len(dp); i++ {
		dp[i][0] = true
	}
	// 初始化第一行
	dp[0][arr[0]] = true
	// 罗列可能性，填写dp表
	for i:=1; i<len(dp); i++ {
		for j:=1; j<=packetSize; j++ {
			// 没有使用当前物品的情况下，上一个物品能否转满j
			dp[i][j] = dp[i-1][j]
			if j - arr[i] >= 0 {
				// 没有使用当前物品的情况下，上一个物品能否转满j-当前物品的重量
				dp[i][j] = dp[i][j] || dp[i-1][j-arr[i]]
			}
		}
	}
	for i:=minUSum+1; i<=packetSize; i++ {
		if !dp[len(arr)-1][i]{
			return i
		}
	}
	return packetSize+1
}


// 3. 进阶，数组中必定含有1，对数组进行排序
//      range 表示 在
// 		对数组进行排序，对与第i个数，如果
//				arr[i] > range 直接返回 arr[i]； arr[i] 必定不是组成和
//				arr[i] <= range range += arr[i]
func UnformedSumPaketMustContainOne(arr []int) int {
	if len(arr) == 0 {
		return 1
	}
	sort.Sort(MyArr(arr))
	pRange := 1
	for i:=1; i<len(arr); i++ {
		if arr[i] > pRange+1 {
			return arr[i]
		} else {
			pRange += arr[i]
		}
	}
	return pRange+1
}

type MyArr []int

func (m MyArr) Len() int {
	return len(m)
}

func (m MyArr) Less(i, j int) bool {
	return m[i] < m[j]
}

func (m MyArr) Swap(i, j int) {
	m[i], m[j] = m[j], m[i]
}
